// 14. 最长公共前缀

// 横向扫描 纵向扫描 分治 二分搜索

/*
编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 ""。

 

示例 1：

输入：strs = ["flower","flow","flight"]
输出："fl"
示例 2：

输入：strs = ["dog","racecar","car"]
输出：""
解释：输入不存在公共前缀。
 

提示：

1 <= strs.length <= 200
0 <= strs[i].length <= 200
strs[i] 仅由小写英文字母组成


来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-common-prefix
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/

/**
 * @param {string[]} strs
 * @return {string}
 * @description 横向扫描
 */
var longestCommonPrefix1 = function (strs) {
	let len = strs.length
	if (!len) return ''
	let prefix = strs[0]
	for (let i = 0; i < len; i++) {
		prefix = longestCommonPrefix(prefix, strs[i])
		if (prefix.length === 0) {
			break
		}
	}
	function longestCommonPrefix(str1, str2) {
		let len = Math.min(str1.length, str2.length),
			index = 0
		while (index < len && str1.charAt(index) === str2.charAt(index)) {
			index++
		}
		return str1.substring(0, index)
	}

	return prefix
}

// console.log(longestCommonPrefix1(['leet1', 'leetcode', 'leea']))

/**
 * @param {string[]} strs
 * @return {string}
 * @description 纵向扫描
 */
var longestCommonPrefix2 = function (strs) {
	if (!strs.length) return ''
	for (let i = 0; i < strs[0].length; i++) {
		let c = strs[0].charAt(i)
		for (let j = 1; j < strs.length; j++) {
			if (i === strs[j].length || strs[j][i] !== c) {
				return strs[0].substring(0, i)
			}
		}
	}
	return strs[0]
}

// console.log(longestCommonPrefix2(['a', 'a', 'ca', 'a']))

/**
 * @param {string[]} strs
 * @return {string}
 * @description 分治法
 */
var longestCommonPrefix3 = function (strs) {
	if (!strs.length) {
		return ''
	} else {
		return longestCommonPrefix(strs, 0, strs.length - 1)
	}
	function longestCommonPrefix(arr, start, end) {
		if (start === end) return arr[start]
		let mid = ~~((start + end) / 2)
		let left = longestCommonPrefix(arr, start, mid)
		let right = longestCommonPrefix(arr, mid + 1, end)
		return commonPrefix(left, right)
	}
	function commonPrefix(left, right) {
		let min = Math.min(left.length, right.length)
		for (let i = 0; i < min; i++) {
			if (left.charAt(i) !== right.charAt(i)) {
				return left.substring(0, i)
			}
		}
		return left.substring(0, min)
	}
}

// console.log(longestCommonPrefix3(['ac', 'ac', 'ac', 'ac']))

/**
 * @param {string[]} strs
 * @return {string}
 * @description 二分查找
 */
var longestCommonPrefix4 = function (strs) {
	if (!strs.length) {
		return ''
	}
	let minLength = strs[0].length
	for (let key in strs) {
		minLength = Math.min(minLength, strs[key].length)
	}

	let low = 0,
		high = minLength
	while (low < high) {
		let mid = ~~((high - low + 1) / 2 + low)
		if (isCommonPrefix(mid)) {
			low = mid
		} else {
			high = mid - 1
		}
	}
	return strs[0].substring(0, low)

	function isCommonPrefix(length) {
		let str0 = strs[0].substring(0, length),
			count = strs.length

		for (let i = 0; i < count; i++) {
			str = strs[i]
			for (let j = 0; j < length; j++) {
				if (str0.charAt(j) !== str.charAt(j)) {
					return false
				}
			}
		}
		return true
	}
}

console.log(longestCommonPrefix4(['acc', 'adcccc', 'acc', 'acc']))
